\documentclass[11pt,italian]{report}

%IMPORTANTE comando \hyphenation{ma-cro-istru-zio-ne nitro-idrossil-amminico} definisce all'algoritmo di latex come spezzare una parola non presente nel suo vocabolario!!

%INCLUSIONE DI PACCHETTI
\usepackage{graphicx}
\usepackage{rotating}
\usepackage{array}
\usepackage{longtable}
\usepackage{multirow}
\usepackage{wrapfig} 
\usepackage{lastpage}
\usepackage{fancyhdr}
\usepackage[english]{babel}
%\usepackage[T1]{fontenc}
%\usepackage[latin9]{inputenc}
\usepackage[colorlinks=true]{hyperref} %per indice con link alle pagine
\usepackage[a4paper,portrait,left=2.5cm,right=2.5cm,bindingoffset=5mm]{geometry}
\usepackage[utf8]{inputenc}
\usepackage{color}
\usepackage{amsmath, amsthm, amssymb}
%\usepackage{xstring}
\hypersetup{colorlinks,citecolor=black,filecolor=black,linkcolor=red,urlcolor=blue}
\setcounter{secnumdepth}{2} % per numerare anche \subsubsection
\setcounter{tocdepth}{2}% per farlo apparire nell'indice
\frenchspacing
\definecolor{LightMagenta}{cmyk}{0.1,0.8,0,0.1}

%HEADER e FOOTER di tutte le pagine tranne quella in cui compare il titolo del capitolo
\pagestyle{fancy}
\fancyhead{}
\headheight = 54pt
\lhead{Computer Science Theory II}
\lfoot{}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
\rhead{\nouppercase{\leftmark}}
\renewcommand{\chaptermark}[1]{\markboth{\thechapter.\ #1}{}}

%HEADER e FOOTER della pagina dove compare il titolo del capitolo
\fancypagestyle{plain}{
%\lhead{\includegraphics[height=50pt]{images/logoUniPd.png}} %IN ALTO A SINISTRA (POTREBBE ANDARE BENE IL LOGO)
\chead{}
\rhead{\bfseries WS2011/12}%\manualeUtenteVer} %IN ALTO A DESTRA
\lfoot{Victor A. Arrascue Ayala Mtr. 3209050\\ Tobias Domhan Mtr.  3202957}
\cfoot{}
\rfoot{Page \thepage{ of} \pageref{LastPage}}
\renewcommand{\headrulewidth}{1pt}
\renewcommand{\footrulewidth}{1pt}
}

\fancypagestyle{romano}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

\fancypagestyle{empty}{
\lhead{}
\chead{}
\rhead{}
\lfoot{}
\cfoot{}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
}

%PAGINA DI PRESETAZIONE DEL DOCUMENTO
\hyphenation{}
\begin{document}


%\begin{center}
%\thispagestyle{empty}
%\huge\textbf{UNIVERSIT\`A degli Studi di PADOVA}\\[2 cm] %GRUPPO DI APPARTENENZA
%\vspace*{0.5in}
%\LARGE\textbf{Titolo del documento}\\[1.0 cm] %TITOLO DEL DOCUMENTO
%\par\rule{10cm}{.5pt} \par
%{\large 12 Ottobre 2009}   %DATA DI CREAZIONE
%\par\rule{10cm}{.10pt} \par
%\vspace*{1.0in}
%\includegraphics[scale=0.30]{images/logoUniPd.png} \\[2cm] %LOGO GRUPPO
%\Large\textbf{Michele Tonon} %AUTORE
%\par\rule{6cm}{.5pt} \par
%\end{center}



% INDEX
%\newpage
%\thispagestyle{romano}
%\pagenumbering{arabic}
%\tableofcontents


%--------------------------------------------- 


%CONTENT


\newpage
\thispagestyle{plain}

\begin{center}
{\Large \textbf{Exercise Sheet 2}}
\end{center}

\noindent{\textbf{Exercise 2.1}}\\\\
(a)\\\\
\begin{equation}
  \label{eq:2}
  \phi = (A \leftrightarrow B) \wedge \neg(C \vee B \rightarrow A)
\end{equation}
$(\leftrightarrow)$-Elimination:
\begin{equation}
  \label{eq:3}
  \equiv (A \rightarrow \neg B) \wedge (\neg B \rightarrow A) \wedge \neg(C \vee B \rightarrow A)
\end{equation}
$(\rightarrow)$-Elimination:
\begin{equation}
  \label{eq:4}
    \equiv (\neg A \vee \neg B) \wedge (B \vee A) \wedge
    \neg(\neg (C \vee B)  \vee A)
\end{equation}
De-Morgan:
\begin{equation}
  \label{eq:5}
  \equiv (\neg A \vee \neg B) \wedge (B \vee A) \wedge  (C \vee B)  \wedge  \neg A
\end{equation}
Distributivity:
\begin{equation}
  \label{eq:10}
    \equiv \neg A \wedge (\neg A \vee \neg B) \wedge (B \vee A) \wedge  (C \vee B)  
\end{equation}
Absorption:
\begin{equation}
  \label{eq:6}
\equiv \neg A \wedge (B \vee A) \wedge (C \vee B)
\end{equation}
Distributivity:
\begin{equation}
  \label{eq:7}
    \equiv ((\neg A \wedge B) \vee (\neg A \wedge A)) \wedge (C \vee B)
\end{equation}
% $\psi \wedge \neg \psi \equiv \perp $
$\psi \wedge \neg \psi \equiv \perp $ 
\begin{equation}
  \label{eq:8}
  \equiv ((\neg A \wedge B) \vee \perp) \wedge (C \vee B)
\end{equation}
$\psi \vee \perp \equiv \psi \equiv \perp \vee \psi $
\begin{equation}
  \label{eq:8}
  \equiv \neg A \wedge B \wedge (C \vee B)
\end{equation}
Absorption:
\begin{equation}
  \label{eq:9}
  \equiv  \neg A \wedge B
\end{equation}
  \\\\\\\\  
(b)\\

i) All cases (X means we \textit{don't care} if it's T or F):\\
\begin{center}
\begin{tabular}{ccccc}
  case & A & B & C & D \\
  1 & T & T & X & X \\
  2 & X & T & T & X \\
  3 & T & T & T & X \\
\end{tabular}
\end{center}
We have four literals. That means overall there are $2^4=16$ different
interpretations. Either side of the \textit{or} must be true. This is
represented by case 1 and case 2. Both account for 4 models
each, because for each there are two literals that either can be true
or false.($2^2=4$) However they are overlapping. This is represented by case 3,
which attributes for 2 models that are counted twice. So overall there
is the models of case 1 plus the ones of case two minus the ones from
case 3:
\begin{equation*}
  4 + 4 -2 = 6
\end{equation*}


ii)
We got an \textit{and} so both sides must be true. For both equivalences
both literals must be true or false. This means A, B and C must be true and D
can take whatever value or  A, B and C must be false and D
can take whatever value. This leaves us with exactly \textbf{four} models.

\vspace {1cm}

\noindent{\textbf{Exercise 2.2}}\\\\
First of all we need to identify the atomic propositions.\\
In the argument we can identify the following indivisible statements:\\\\
A: Alice is elected class-president\\
B: Betty is elected vice-president\\
C: Carol is elected treasurer\\
The propositional variables A, B and C are abstractions of the above mentioned statements.\\\\
The argument can be also be divided in different parts, being the first one:\\
``If Alice is elected class-president, then either Betty is elected vice-president, or Carol is elected treasurer.''\\
This can be in propositional logic written as:\\
A$\rightarrow$ B $\vee$ C\\
The second part is:\\
``Betty is elected vice-president. Therefore if Alice is elected class- president, then Carol is not elected treasurer.''\\
First of all, ``Betty is elected vice-president" states that B is true. Therefore we write:\\
B\\
``if Alice is elected class- president, then Carol is not elected
treasurer" can be formalized like this:\\
A$\rightarrow$$\neg$C\\
The word "therefore" is here connecting all the previous statements with the last one.
As a consequence, the whole argument can be formalized like the following:\\
((A$\rightarrow$ (B $\vee$ C)) $\wedge$ B) $\rightarrow$ (A$\rightarrow$$\neg$C) (*)\\\\
To prove if the argument is invalid, we need to find one case in which the whole argument (*) is false. Considering that this is an implication, we need to find an interpretation which makes the statement left of the implication TRUE and right of the implication FALSE.\\\\
Starting from A$\rightarrow$$\neg$C (the right statement), the only interpretation which makes it false is:\\
I = \{A $\rightarrow$ T, C $\rightarrow$ T\}\\
If we consider the the left statement, it is not difficult to see that it is TRUE whenever B is TRUE. In this way the following interpretation:\\
I = \{A $\rightarrow$ T, B $\rightarrow$ T, C $\rightarrow$ T\}\\
provides the prove we needed for the invalidity.
 

\end{document}

